[USACO07FEB]银牛派对Silver Cow Party
题意:
有$n$头牛,$m$条路,所有牛要前往$X$牛的家开趴(当然$X$牛不用动),求其他牛去开趴来回的最短距离,输出最长的那条。
简化版题意:
有$n$个节点,$m$条边,给出终点$X$,求其他节点到终点的来回最短距离,输出最长的距离。
注意:该题所给的边为有向边,别瞎*2输出
使用的算法:SPFA
思路:
题目要找其他点到终点$X$的最短路径和终点$X$到其他点的最短路径。为便于代码实现,要进行反向建图,用SPFA跑正向的图求终点$X$到其他点的最短路径,再用跑反向图求其他点到终点$X$的最短路径。
反向图即将边的起点和终点反过来,边权不变。
1 |
|